//滑动窗口最大值
class Solution {

public:
    typedef pair<int, int> PII;

    struct comp {
        bool operator()(const PII& x, const PII& y) { return x < y; }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<PII, vector<PII>, comp> heap;
        vector<int> ret;
        for (int i = 0; i < k; i++) {
            heap.push({nums[i], i});
        }
        ret.push_back(heap.top().first);
        for (int i = k; i < nums.size(); i++) {
            heap.push({nums[i], i});
            while (heap.top().second <= i - k) {
                heap.pop();
            }
            ret.push_back(heap.top().first);
        }
        return ret;
    }
};

//最小覆盖子串
class Solution {
public:
    typedef pair<int, int> PII;
    string minWindow(string s, string t) {
        int hash[128] = {0};
        int _hash[128] = {0};
        PII ret = {-1, s.size() + 1};

        for (auto& ch : t) {
            hash[ch]++;
        }

        int left = 0;
        int right = 0;
        int n = s.size();
        int count = 0;
        while (right < n) {
            if (++_hash[s[right]] <= hash[s[right]])
                count++;
            while (count == t.size()) {
                if (ret.second > right - left + 1) {
                    // ret = string(s.begin() + left,s.begin() + right + 1);
                    ret.first = left;
                    ret.second = right - left + 1;
                }
                if (_hash[s[left]]-- <= hash[s[left]])
                    count--;
                left++;
            }
            right++;
        }
        if (ret.first == -1)
            return "";
        return s.substr(ret.first, ret.second);
    }
};